package com.hanxiaozhang.no10leetcode.tree;

import com.hanxiaozhang.no10leetcode.link.Node;

/**
 * 〈一句话功能简述〉<br>
 * 〈按升序排列的链表转化为平衡搜索二叉树〉
 * <p>
 * 思路：
 * 1.整体使用递归构建树，找到中间结点，中间左侧为左孩子子树，中间右侧为右孩子子树
 * 2.找中间位置时，链表快速找中间位置使用快慢指针，主要注意循环条件（fast != tail && fast.next != tail）。
 *
 * @author hanxinghua
 * @create 2024/4/12
 * @since 1.0.0
 */
public class No109ConvertSortedListToBST {

    public static void main(String[] args) {

        // {-10, -3, 0, 5, 9};

        Node<Integer> link = new Node(-10);
        link.next = new Node(-3);
        link.next.next = new Node(0);
        link.next.next.next = new Node(5);
        link.next.next.next.next = new Node(9);


        TreeNode tree = method1(link);
        System.out.println();

    }

    /**
     * 方法1
     * 思路：
     * 1.整体使用递归构建树，找到中间结点，中间左侧为左孩子子树，中间右侧为右孩子子树
     * 2.找中间位置时，链表快速找中间位置使用快慢指针，主要注意循环条件（fast != tail && fast.next != tail）。
     *
     * @param head
     * @return
     */
    private static TreeNode method1(Node head) {
        if (head == null) {
            return null;
        }

        return recursion(head, null);
    }

    private static TreeNode recursion(Node head, Node tail) {

        if (head == tail) {
            return null;
        }

        // 快慢指针中，slow代表1/2处节点
        Node<Integer> slow = head;
        Node<Integer> fast = head;
        // 特殊点，循环条件：fast != tail && fast.next != tail
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode node = new TreeNode(slow.data);
        node.left = recursion(head, slow);
        node.right = recursion(slow.next, tail);
        return node;
    }




    /*
    这道题给大家提供一个链表的通用思路，首先用链表重建和用数组重建的主要区别是啥？
    我们回忆一下用数组重建的过程，由于数组我们可以获取长度，所以很容易找到mid值，但是链表就不一样了，
    无法直接获取链表长度，除非你的数据结构里特殊处理过，那么我们怎么快速找到链表中点呢？
    有一个好办法就是快慢指针，一个一次走两步，一个一次走一步，当快指针走到了tail的时候就停，
    此时慢指针所指的就是中点，找到中点之后的处理肯定又是递归啦，和数组处理上就没有什么区别了。
     */
}
